﻿#define _CRT_SECURE_NO_WARNINGS


/*给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

示例 1:

输入: 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。
*/
int findIntegers(int num)
{
	if (num < 2)
		return num + 1;
	int f[30];
	f[0] = 1;
	f[1] = 2;
	for (int i = 2; i < 30; i++)
	{
		f[i] = f[i - 1] + f[i - 2];
	}
	int ans = 0;
	for (int i = 29; i >= 0; i--)
	{
		if ((num >> i) & 1)
		{
			ans += f[i];
			if (num >> (i + 1) & 1)
			{
				return ans;
			}
		}
	}
	return ans + 1;
}
//#include<stdio.h>
//int main()
//{
//	char* a[] = { "work","at","alibaba" };
//	char** pa = a;
//	pa++;
//	printf("%s\n", *pa);//打印at
//	printf("%c\n", **pa);//打印a
//	return  0;
//}